"""
    python实现链式栈模型
    目标: 栈(LIFO 后进先出)
    设计:
      栈底: 链表尾部作为栈底
      栈顶: 链表头部作为栈顶,负责入栈和出栈操作
           入栈: 在链表头部添加一个节点
           出栈: 删除链表头节点
"""


class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None


class LinkStack:
    def __init__(self):
        """
        初始化一个空栈: 等价于初始化一个空链表
        """
        self.head = None

    def push(self, item):
        """
        入栈: 链表头部添加一个节点
        """
        node = ListNode(item)
        node.next = self.head
        self.head = node

    def pop(self):
        """
        出栈: 删除链表头节点
        :return: 出栈的数据元素
        """
        if not self.head:
            raise Exception("pop from empty LinkStack")

        element = self.head.val
        self.head = self.head.next

        return element


if __name__ == '__main__':
    ls = LinkStack()
    # 入栈: 100 200 300
    ls.push(100)
    ls.push(200)
    ls.push(300)
    # 出栈: 300 200 100 异常
    print(ls.pop())
    print(ls.pop())
    print(ls.pop())
    print(ls.pop())










